The use of Computing Devices (CDs) and computer networks are an integral part of personal, corporate and government communication. A computer network is a collection of physically distributed sub-networks, such as local area networks (LANs) that transport data between network nodes. A node may be loosely defined as a device adapted to send and/or receive data in the computer network. Therefore, a node may be the source of data to be transported, the destination for data being transported or a location through which data may travel on its way from source to destination.
Network topology is the representation and arrangement of network elements, including links and nodes, and the physical and logical interconnections between nodes. A LAN is an example of a network that exhibits both a physical topology and a logical topology. Any given node in a LAN will have one or more physical links to one or more other nodes in the network typically through one or more intermediate nodes, such as routers and switches, thus defining the physical topology. Likewise, the mapping of the flow of data between the nodes in the network determines the logical topology of the network. The physical and logical topologies might be identical in any particular network, but they also may be different.
Data may be exchanged via intra-network communications, that is within one network, and may also be exchanged inter-network, that is between neighboring (i.e., logically and/or physically adjacent) networks. In that regard, “edge devices” located at the logical outer boundaries of the computer network may be adapted to send and receive internetwork communications. Both inter-network and intra-network communications are typically effected by exchanging discrete packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how network nodes interact with each other.
FIG. 1 is a schematic of an illustrative prior art Virtual Private Network (VPN) 100, as is well known by those skilled in the art. A VPN is a computer network that is a collection of network nodes that establish private communications over a shared backbone network. VPNs effectively tunnel through another network for security reasons or to separate traffic from various users. Routing devices, generically referred to by their primary purpose, such as customer edge routers, core routers and the like, utilize a defined protocol that specifies how routers will communicate with other routers to receive and send information via selected routes between nodes on a network. The term routing protocol may refer more specifically to a protocol operating at Layer 3 of the Open Systems Interconnection (OSI) model, which distributes network topology information among routers.
Referring to FIG. 1, Customer Edge (CE1 and CE2) routers 102 located at a customer premises, are in turn are connected to Provider Edge (PE1 and PE2) routers 104 of a service provider Internet Protocol/Multiple Protocol Label Switching (IP/MPLS) network. CE routers communicate or peer with the PE routers through a corresponding Virtual Routing and Forwarding (VRF) attachment circuit. The PE router resides between one network service provider's area and areas administered by other network providers.
In Multi-Protocol Label Switching (MPLS) networks, a P router (106), which is typically referred to as a provider core router, is a Label Switch Router (LSR) that functions as a transit router of the core network. A PE router is typically connected to one or more P routers. In the illustrative network 100 of FIG. 1, six P routers 106 (P1, P2, P3, . . . P6) are shown, with each PE router 104 (PE1, PE2), connected by a physical link to core routers P1, P2 and P3, P4, respectively.
In the current state of the art, the provider edge routers 104 (PE1, PE2) utilize the internal Border Gateway Protocol (iBGP) to exchange routing information. The routing information typically includes destination address prefixes and associated path attributes. The routing information via iBGP is exchanged via a Route Reflector (RR) 108 in a manner well known in the art. An Interior Gateway Protocol (IGP) is then employed to resolve traffic routing within an autonomous system, here shown as the paths between the provider edge routers 104 (PE1, PE2) via the core routers 106 (P1, P2, P3, . . . P6). One type of IGP is a link-state routing protocol which includes the open shortest path first (OSPF) and the intermediate system-to-intermediate system (IS-IS) protocols. In link-state routing protocols, each node possesses information about the complete network topology. Each node then independently calculates the best path or next hop from it for every possible destination in the network using local information of the topology. The collection of best next hops forms the routing table for the node. Another type of IGP is a distance-vector routing protocol, which works by having each router advertise its distances from other routers and receiving similar advertisements from other routers such that each router populates its routing table. This process continues in cycles until the routing tables of each router converge to stable values.
The Link-state advertisement (LSA) is a basic communication means of the OSPF routing protocol. It advertises or communicates the router's local routing topology to all other local routers in the same OSPF area. OSPF is designed for scalability, so some LSAs are not flooded out on all peered links, but only on those that belong to the appropriate area. In this way detailed information can be kept localized, while summary information is flooded to the rest of the network. Nevertheless, as provider edge routers are added to the network, a very large amount of state information needs to be maintained.
In current networks, where every node is treated as an equal IGP peer, every link failure, including a PE-P link failure, causes a network-wide reconvergence event. The current methodology for minimizing outages from link failures is known as MPLS Fast Re-Route (FRR). With reference to FIG. 2, in accordance with FRR, a primary tunnel is established between core router 206 P2 and provider edge router 204 PE1. A backup tunnel for P2-P1-PE1 is preconfigured in the event of a primary tunnel failure. However, such tunnels require that all PE routers be part of the IGP. When a primary tunnel fails (i.e., the link between P2 and PE1), traffic is automatically sent through the preconfigured backup tunnel. Additionally, a network-wide IGP reconvergence event is thereafter triggered due to the physical link failure that caused the primary tunnel failure, causing additional traffic to be rerouted and another traffic hit.
FIG. 3 shows a full mesh of Fast Re-Route tunnels between routers PE2 and PE1 304 via a defined set of core routers 306. In accordance with this configuration, a primary tunnel is established for steady-state traffic flow utilizing core routers 306, P4-P6-P2. Additionally, a backup tunnel utilizing core routers 306, P3-P5-P1 is established in the event of a primary tunnel failure. Furthermore the process of establishing primary and backup tunnel is repeated for all other PEs in a given network. Label distribution Protocol (LDP) is a protocol which relies on underlying routing information provided by the IGP in order to forward label packets which are ultimately used to forward traffic through MPLS networks. The tunnels, both primary and backup, can be setup automatically or statically. When the primary tunnel fails, traffic is automatically sent through the backup tunnel. Just as in the case of MPLS Fast Re-Route (FRR) of FIG. 2, when a full mesh of Fast Re-Route tunnel configuration of FIG. 3 is utilized, and when the primary tunnel fails, traffic is automatically sent through the preconfigured backup tunnel and a network-wide IGP reconvergence event is thereafter triggered, causing additional traffic to be rerouted and another traffic hit.
It would therefore be desirable to eliminate reconvergence events for PE-P link failures by taking advantage of an architecture having a pre-defined “mated pair” of core routers for each PE router where the PE-P links reside outside of the IGP. To the inventors' knowledge, no such system or method currently exists.